UnivTrevesV1, Main, Exploration, bibRecord, 000B16

An exact algorithm for the Maximum Leaf Spanning Tree problem

Identifieur interne : 000B16 ( Main/Exploration ); précédent : 000B15; suivant : 000B17

An exact algorithm for the Maximum Leaf Spanning Tree problem

Auteurs : Henning Fernau [Allemagne] ; Joachim Kneis [Allemagne] ; Dieter Kratsch [France] ; Alexander Langer [Allemagne] ; Mathieu Liedloff [France] ; Daniel Raible [Allemagne] ; Peter Rossmanith [Allemagne]

Source :

Theoretical computer science [ 0304-3975 ] ; 2011.

RBID : Pascal:11-0454165

Descripteurs français

Pascal (Inist)
- Informatique théorique, Maximum, Arbre maximal, Ramification, Ensemble dominant, Borne inférieure, 68Wxx, 68R10, Temps exponentiel, Pire cas, Algorithme graphe.

English descriptors

KwdEn :
- Branching, Computer theory, Dominating set, Graph algorithm, Lower bound, Maximum, Spanning tree.

Abstract

Given an undirected graph with n vertices, the MAXIMUM LEAF SPANNING TREE problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4^kpoly(n)) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008 [16]). Daligault et al. (2010) [6] improved the branching and obtained a running time of O(3.72^kpoly(n)). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the CONNECTED DOMINATING SET problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Ω(2ⁿ) barrier and proposed an O(1.9407ⁿ)-time algorithm (Fomin et al. 2008 [11]). Based on some useful properties of Kneis et al. (2008) [16] and Daligault et al. (2010) [6], we present a branching algorithm whose running time of 0(1.8966") has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Ω(1.4422ⁿ) for the worst case running time of our algorithm.

Affiliations:

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000376
to stream PascalFrancis, to step Curation: 000975
to stream PascalFrancis, to step Checkpoint: 000333
to stream Main, to step Merge: 000B66
to stream Main, to step Curation: 000B16

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">An exact algorithm for the Maximum Leaf Spanning Tree problem</title>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Universität Trier, FB 4-Abteilung Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>FB 4-Abteilung Informatik</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
<author><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Computer Science, RWTH Aachen University</s1>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
<sZ>4 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>RWTH Aachen University</wicri:noRegion>
<wicri:noRegion>Department of Computer Science, RWTH Aachen University</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation wicri:level="4"><inist:fA14 i1="03"><s1>Laboratoire d'Informatique Théorique et Appliquée, Université Paul Verlaine - Metz</s1>
<s2>57045 Metz</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Metz</settlement>
</placeName>
<orgName type="university">Université Paul Verlaine - Metz</orgName>
</affiliation>
</author>
<author><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Computer Science, RWTH Aachen University</s1>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
<sZ>4 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>RWTH Aachen University</wicri:noRegion>
<wicri:noRegion>Department of Computer Science, RWTH Aachen University</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name>
<affiliation wicri:level="4"><inist:fA14 i1="04"><s1>Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans</s1>
<s2>45067 Orléans</s2>
<s3>FRA</s3>
<sZ>5 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Centre-Val de Loire</region>
<region type="old region" nuts="2">Région Centre</region>
<settlement type="city">Orléans</settlement>
</placeName>
<orgName type="university">Université d'Orléans</orgName>
</affiliation>
</author>
<author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Universität Trier, FB 4-Abteilung Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>FB 4-Abteilung Informatik</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Computer Science, RWTH Aachen University</s1>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
<sZ>4 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>RWTH Aachen University</wicri:noRegion>
<wicri:noRegion>Department of Computer Science, RWTH Aachen University</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">11-0454165</idno>
<date when="2011">2011</date>
<idno type="stanalyst">PASCAL 11-0454165 INIST</idno>
<idno type="RBID">Pascal:11-0454165</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000376</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000975</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000333</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000333</idno>
<idno type="wicri:doubleKey">0304-3975:2011:Fernau H:an:exact:algorithm</idno>
<idno type="wicri:Area/Main/Merge">000B66</idno>
<idno type="wicri:Area/Main/Curation">000B16</idno>
<idno type="wicri:Area/Main/Exploration">000B16</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">An exact algorithm for the Maximum Leaf Spanning Tree problem</title>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Universität Trier, FB 4-Abteilung Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>FB 4-Abteilung Informatik</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
<author><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Computer Science, RWTH Aachen University</s1>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
<sZ>4 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>RWTH Aachen University</wicri:noRegion>
<wicri:noRegion>Department of Computer Science, RWTH Aachen University</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation wicri:level="4"><inist:fA14 i1="03"><s1>Laboratoire d'Informatique Théorique et Appliquée, Université Paul Verlaine - Metz</s1>
<s2>57045 Metz</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Metz</settlement>
</placeName>
<orgName type="university">Université Paul Verlaine - Metz</orgName>
</affiliation>
</author>
<author><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Computer Science, RWTH Aachen University</s1>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
<sZ>4 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>RWTH Aachen University</wicri:noRegion>
<wicri:noRegion>Department of Computer Science, RWTH Aachen University</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name>
<affiliation wicri:level="4"><inist:fA14 i1="04"><s1>Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans</s1>
<s2>45067 Orléans</s2>
<s3>FRA</s3>
<sZ>5 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Centre-Val de Loire</region>
<region type="old region" nuts="2">Région Centre</region>
<settlement type="city">Orléans</settlement>
</placeName>
<orgName type="university">Université d'Orléans</orgName>
</affiliation>
</author>
<author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Universität Trier, FB 4-Abteilung Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>FB 4-Abteilung Informatik</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Computer Science, RWTH Aachen University</s1>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
<sZ>4 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>RWTH Aachen University</wicri:noRegion>
<wicri:noRegion>Department of Computer Science, RWTH Aachen University</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
<imprint><date when="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Branching</term>
<term>Computer theory</term>
<term>Dominating set</term>
<term>Graph algorithm</term>
<term>Lower bound</term>
<term>Maximum</term>
<term>Spanning tree</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term>
<term>Maximum</term>
<term>Arbre maximal</term>
<term>Ramification</term>
<term>Ensemble dominant</term>
<term>Borne inférieure</term>
<term>68Wxx</term>
<term>68R10</term>
<term>Temps exponentiel</term>
<term>Pire cas</term>
<term>Algorithme graphe</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Given an undirected graph with n vertices, the MAXIMUM LEAF SPANNING TREE problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4<sup>k</sup>
poly(n)) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008 [16]). Daligault et al. (2010) [6] improved the branching and obtained a running time of O(3.72<sup>k</sup>
poly(n)). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the CONNECTED DOMINATING SET problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Ω(2<sup>n</sup>
) barrier and proposed an O(1.9407<sup>n</sup>
)-time algorithm (Fomin et al. 2008 [11]). Based on some useful properties of Kneis et al. (2008) [16] and Daligault et al. (2010) [6], we present a branching algorithm whose running time of 0(1.8966") has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Ω(1.4422<sup>n</sup>
) for the worst case running time of our algorithm.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>France</li>
</country>
<region><li>Centre-Val de Loire</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Rhénanie-Palatinat</li>
<li>Région Centre</li>
</region>
<settlement><li>Metz</li>
<li>Orléans</li>
<li>Trèves (Allemagne)</li>
</settlement>
<orgName><li>Université Paul Verlaine - Metz</li>
<li>Université d'Orléans</li>
<li>Université de Trèves</li>
</orgName>
</list>
<tree><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
</region>
<name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name>
<name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name>
<name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name>
<name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name>
</country>
<country name="France"><region name="Grand Est"><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
</region>
<name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000B16 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000B16 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:11-0454165
   |texte=   An exact algorithm for the Maximum Leaf Spanning Tree problem
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

An exact algorithm for the Maximum Leaf Spanning Tree problem

An exact algorithm for the Maximum Leaf Spanning Tree problem

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri